1. Technical Field
The present invention relates in general to rendering in data processing system displays and in particular to rendering primitives processed as multiple, parallel horizontal or vertical scan lines. Still more particularly, the present invention relates to optimizing frame buffer utilization during rendering by minimizing page boundary crossings.
2. Description of the Related Art
Rendering within data processing systems is the process of generating two dimensional images of data for display on a monitor. Typically, rendering includes processing geometric primitives (e.g., points, lines and polygons) to determine component pixel values for the monitor display, a process often referred to specifically as rasterization.
The pixels for the display area of a data processing system monitor are conventionally viewed as a matrix. The pixel matrix and/or the frame buffer, which stores rendered pixel information from which the display is refreshed, are typically partitioned for manageability. Pixel information may be partitioned in a contiguous fashion as illustrated in FIG. 5A, with all data within a frame buffer or frame buffer partition corresponding to a contiguous region of adjacent pixels, or in an interleaved fashion as illustrated in FIG. 5B, with each frame buffer containing every nth pixel of every mth line in the matrix. A 4.times.1 interleaved partitioning of display pixels to frame buffers is depicted in FIG. 5B.
Rendering primitives to generate frame buffer data typically involves dividing the primitive into scan lines, single-pixel thick horizontal or vertical regions of the primitive. Scan lines are also referred to as spans, a term used interchangeably to refer to a scan line or the series of adjacent pixels which make up a scan line. FIG. 5C depicts two horizontal scan lines defined by endpoint pixels P.sub.0 (i)-P.sub.n (i) and P.sub.0 (i+1)-P.sub.n (i+1) within a primitive defined by vertices V.sub.1, V.sub.2, and V.sub.3. Although the primitive in the example shown in FIG. 5C is divided into horizontal scan lines, vertical scan lines may be utilized with no greater complexity, and frequently are employed.
When rendering, conventionally a scan line is started from an initial point P.sub.0 (i) and rendered along the scan line until the end of the span is reached at P.sub.n (i). The next scan line is then begun at an initial point P.sub.0 (i+1) at the same end as the point at which the previous scan line was started, and the next scan line is rendered in the same direction as the previous scan line. Scan lines may be rendered a single pixel at a time, or multiple adjacent pixels may be rendered concurrently so that the scan line is rendered in unit of m pixels. Additionally, multiple scan lines may be rendered in parallel, so that m pixels of n scan lines are processed concurrently, then the next m pixels of the same n scan lines are rendered, and so forth until the end of the scan line is reached, when the next n adjacent scan lines are started. Thus, the primitive is effectively rendered in as many blocks of n.times.m pixels as is required.
One problem in rendering primitives as described above is that the fill rate for the primitive is directly associated with frame buffer utilization. Each frame buffer or frame buffer partition may contain multiple memory pages. If the pixel information for pixels within a scan line bridges a page boundary within the frame buffer or frame buffer partition, rendering a primitive may require multiple frame buffer page-ins and page-outs per scan line. Each time a page boundary is crossed and frame buffer pages must be paged-in or paged-out of the cache, a substantial performance penalty is incurred. The greater the number of memory page crossings, the lower the performance of the rendering system and the lower the primitive fill rate.
Cache techniques may improve rendering performance by delay frame buffer memory accesses. However, the cache itself is typically mapped directly to the frame buffer(s) in a tiled fashion (that is, where each cache segment containing pixel information for multiple pixel segments, where scan lines are rendered a pixel segment at a time), and is not dynamically resizable for rendering individual primitives.
It would be desirable, therefore, to provide a mechanism for rendering primitives which minimized page crossing during rendering of primitive scan lines.